Theory Lunch

Title Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries

Jingxun Liang

January 29, 2025 (GHC 8102)

Abstract: The dictionary problem involves maintaining a set $S \subset [U]$ of n keys under insertions, deletions, and membership queries focusing on efficiency in both time and space. This fundamental problem has been studied extensively for six decades since 1953. Recently, a series of works has established the optimal time-space trade-off for dictionaries. In this talk, I will describe the tight lower bound result that any dictionary with an operational time $t$ must incur a redundant $\Omega(log^{(t)} n)$ bits per key in space.